package com.feiyu.search;

/**
 * @Author nanshouxiao@teacher.com.cn
 * @Date 2017-10-30 12:29
 */
public class HalfSearch {
    public static void main(String[] args) {
        int arrayLength = 210000000;
        int[] array = new int[arrayLength];
        for (int i = 0; i < arrayLength; i++) {
            array[i] = i;
        }
        int value = 200000000;
        HalfSearch h = new HalfSearch();
        long time1 = System.currentTimeMillis();
        System.out.println(h.search2(array,value));
        long time2 = System.currentTimeMillis();
        System.out.println("search2 use " + (time2 - time1));
        System.out.println(h.search(array,value));
        System.out.println("search1 use " + (System.currentTimeMillis() - time2));
    }

    private int search2(int[] array, int value) {
        int arraylength = array.length;
        for (int i = 0; i < arraylength; i++) {
            if (array[i] == value) {
                return i;
            }
        }
        return -1;
    }

    /**
     * 二分法查找
     * @param array
     * @param value
     * @return
     */
    private int search(int[] array, int value) {
        boolean isEnd = false;
        int length = array.length;
        if (length < 0) {
            return -1;
        }
        if (length == 1) {
            return array[0] == value ? 0 : -1;
        }
        int left = 0;
        int right = length;
        int deep = 0;
        while (!isEnd) {
            deep++;
            System.out.println("use deep " + deep);
            int index = (left + right)/2;
            int tempValue = array[index];
            if (tempValue == value) {
                return index;
            } else if(value > tempValue){
                left = index;
            } else if(value < tempValue){
                right = index;
            }
            isEnd = right - left <= 1;
        }
        return -1;
    }
}
